package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0321_01 {

    /**
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，
     * 否则返回 false。假设输入的数组的任意两个数字都互不相同。
     *
     * 输入: [1,6,3,2,5]
     * 输出: false
     *
     * 输入: [1,3,2,6,5]
     * 输出: true
     *
     * @param postorder
     * @return
     */
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length - 1);
    }

    /**
     * 1、函数定义：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
     *
     * @param postorder
     * @param left      左指针
     * @param right     右指针
     * @return 如果是则返回 true
     */
    private boolean recur(int[] postorder, int left, int right) {
        // 2、寻找递归结束的条件
        // 左右指针重合的时候，即left~right区间只有一个数字
        if (left >= right) {
            return true;
        }
        // 在后续遍历中根节点一定是最后一个点
        int root = postorder[right];
        int index = left;
        // 此时不会等于 题目要求说 该数组中没有重复的元素
        while (postorder[index] < root) {
            index++;
        }
        int m = index; // left~right之间第一个比root大的点，即root右字数中最小的点（右字数后序遍历的起点）
        // 如果 m~right区间（root的右子树）中出现了比root小的节点，则不可能是后续遍历
        while (index < right) {
            if (postorder[index] < root) {
                return false;
            }
            index++;
        }
        // 3、找到函数的等价关系式 左右子树都是后续遍历的结果，证明 该数组是 某二叉搜索树的后序遍历结果
        // 此时能够保证 left~ m-1 都比root小，m~right-1 都比root大，但这两个子区间内部的情况需要继续递归判断
        return recur(postorder, left, m - 1) && recur(postorder, m, right - 1);
    }

//    public boolean verifyPostorder(int[] postorder) {
//        return recur(postorder, 0, postorder.length - 1);
//    }
//
//    private boolean recur(int[] postorder, int left, int right) {
//        //（结束条件最后看！）左右指针重合的时候，即left~right区间只有一个数
//        if (left >= right) {
//            return true;
//        }
//        //在后序遍历中根节点一定是最后一个点
//        int root = postorder[right];
//        int index = left;
//        while (postorder[index] < root) {
//            index++;
//        }
//        int m = index;//left~right之间第一个比root大的点，即root右子树中最小的点（右子树后序遍历的起点）
//        //如果m~right区间（root的右子树）出现了比root小的节点，则不可能是后序遍历
//        while (index < right) {
//            if (postorder[index] < root) {
//                return false;
//            }
//            index++;
//        }
//        //此时能保证left ~ m-1都比root小，m ~ right-1都比root大，但这两个子区间内部的情况需要继续递归判断
//        return recur(postorder, left, m - 1) && recur(postorder, m, right - 1);
//    }


    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
